<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>OpenMesh: The Halfedge Data Structure</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="logo_align.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="rwth_vci_rgb.jpg"/></td>
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">OpenMesh
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('a04322.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">The Halfedge Data Structure </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>This section describes the underlying data structure that is used to store the mesh entities (items) vertices, edges, faces, and their connectivity information.</p>
<p>There are many popular data structures used to represent polygonal meshes. For a detailed comparison of them refer to the papers at the end of this section.</p>
<p>The data structure used in this project is the so called <em> halfedge data structure </em>. While <em> face-based </em> structures store their connectivity in faces referencing their vertices and neighbors, <em> edge-based </em> structures put the connectivity information into the edges. Each edge references its two vertices, the faces it belongs to and the two next edges in these faces. If one now splits the edges (i.e. an edge connecting vertex <code>A</code> and vertex <code>B</code> becomes two <em> directed halfeges </em> from <code>A</code> to <code>B</code> and vice versa) one gets a <em> halfedge-based </em> data structure. The following figure illustrates the way connectivity is stored in this structure:</p>
<table class="doxtable">
<tr valign="top">
<td><div class="image">
<img src="halfedge_structure3.png" alt="halfedge_structure3.png"/>
</div>
 </td><td><ul>
<li>
Each <b>vertex</b> references one outgoing halfedge, i.e. a halfedge that starts at this vertex (1). </li>
<li>
Each <b>face</b> references one of the halfedges bounding it (2). </li>
<li>
Each <b>halfedge</b> provides a handle to <ul>
<li>
the vertex it points to (3), </li>
<li>
the face it belongs to (4) </li>
<li>
the next halfedge inside the face (ordered counter-clockwise) (5), </li>
<li>
the opposite halfedge (6), </li>
<li>
(optionally: the previous halfedge in the face (7)). </li>
</ul>
</li>
</ul>
</td></tr>
</table>
<p>Having these links between the items, it is now possible to circulate around a face in order to enumerate all its vertices, halgedges, or neighboring faces. When starting at a vertex' halfedge and iterating to the opposite of its previous one, one can easily circulate around this vertex and get all its one-ring neighbors, the incoming/outgoing halfedges, or the adjacent faces. All this functionality is encapsulated into the so-called <em> circulators </em>, described in <a class="el" href="a04328.html">Mesh Iterators and Circulators</a>.</p>
<dl class="section attention"><dt>Attention</dt><dd>In order to efficiently classify a boundary vertex, the outgoing halfedge of these vertices <b> must be a boundary halfedge </b> (see OpenMesh::PolyMeshT::is_boundary()). </dd>
<dd>
Whenever you modify the topology using low-level topology changing functions, be sure to guarantee this behaviour (see OpenMesh::PolyMeshT::adjust_outgoing_halfedge())</dd></dl>
<p>While one does not need to store the previous halfedge (7) explicitly, because it can be derived from the links to the next halfedges, one may do so for the sake of performance. In fact, the previous halfedge is stored by default (<a class="el" href="a02469.html" title="Base class for all traits. ">OpenMesh::DefaultTraits</a>). Using traits and attributes the previous halfedge can removed, to gain memory. This kind of mesh customization is explained in <a class="el" href="a04324.html">Specifying your MyMesh</a>.</p>
<p>While the halfedge-based structures usually consume more memory than their face-based counter-parts they have the following important advantages:</p>
<ul>
<li>It is easy to mix faces of arbitrary vertex count in one mesh.</li>
</ul>
<ul>
<li>We now have an explicit representation of vertices, faces, <em>and</em> edges/halfedges. This becomes extremely useful if one has to store data per edge/halfedge since this can easily be modelled by member variables of these types (see <a class="el" href="a04324.html">Specifying your MyMesh</a>).</li>
</ul>
<ul>
<li>Circulating around a vertex in order to get its one-ring neighbors is an important operation for many kinds of algorithms on polygonal meshes. For face-based structures this leads to many <code>if-then</code> branchings, the halfedge structure provides this funcionality without conditional branching in constant time.</li>
</ul>
<p><b>References</b></p>
<p>S. Campagna, L. Kobbelt, H.-P. Seidel, <em> Directed Edges - A Scalable Representation For Triangle Meshes </em>, ACM Journal of Graphics Tools 3 (4), 1998.</p>
<p>Lutz Kettner, <em> Using Generic Programming for Designing a Data Structure for Polyhedral Surfaces</em>, in Proc. 14th Annual ACM Symp. on Computational Geometry, 1998. </p>
</div></div><!-- contents -->
</div><!-- doc-content -->
<hr>
<address>
<small>
<a href="http://www.rwth-graphics.de" style="text-decoration:none;">
</a>
Project <b>OpenMesh</b>, 
&copy;&nbsp; Computer Graphics Group, RWTH Aachen.
Documentation generated using 
<a class="el" href="http://www.doxygen.org/index.html">
<b>doxygen</b>
</a>.
</small>
</address>
</body>
</html>
